use std::{cell::RefCell, fmt, rc::Rc};

#[derive(Clone)]
pub struct MergeableHeapNode<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> {
    p: RefCell<Option<Rc<MergeableHeapNode<T>>>>,
    key: RefCell<T>,
    child: RefCell<Option<Rc<MergeableHeapNode<T>>>>,
    left: RefCell<Option<Rc<MergeableHeapNode<T>>>>,
    right: RefCell<Option<Rc<MergeableHeapNode<T>>>>,
    degree: RefCell<u32>,
    mark: RefCell<bool>,
}
impl<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> MergeableHeapNode<T> {
    pub fn build(k: T) -> Rc<MergeableHeapNode<T>> {
        Rc::new(MergeableHeapNode {
            p: RefCell::new(None),
            key: RefCell::new(k),
            child: RefCell::new(None),
            left: RefCell::new(None),
            right: RefCell::new(None),
            degree: RefCell::new(0),
            mark: RefCell::new(false),
        })
    }
    pub fn get_p(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        unsafe {
            if let Some(v) = &*(self.p.as_ptr()) {
                Some(Rc::clone(v))
            } else {
                None
            }
        }
    }
    pub fn get_key(&self) -> T {
        unsafe { (*(self.key.as_ptr())).clone() }
    }
    pub fn get_child(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        unsafe {
            if let Some(v) = &*(self.child.as_ptr()) {
                Some(Rc::clone(v))
            } else {
                None
            }
        }
    }
    pub fn get_left(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        unsafe {
            if let Some(v) = &*(self.left.as_ptr()) {
                Some(Rc::clone(v))
            } else {
                None
            }
        }
    }
    pub fn get_right(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        unsafe {
            if let Some(v) = &*(self.right.as_ptr()) {
                Some(Rc::clone(v))
            } else {
                None
            }
        }
    }
    pub fn get_degree(&self) -> u32 {
        unsafe { *(self.degree.as_ptr()) }
    }
    pub fn get_mark(&self) -> bool {
        unsafe { *(self.mark.as_ptr()) }
    }

    pub fn is_alone(&self) -> bool {
        self.get_left().is_none() && self.get_right().is_none()
    }

    pub fn set_p(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        *(self.p.borrow_mut()) = v;
    }
    pub fn set_key(&self, v: T) {
        *(self.key.borrow_mut()) = v;
    }
    pub fn set_child(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        *(self.child.borrow_mut()) = v;
    }
    pub fn set_left(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        *(self.left.borrow_mut()) = v;
    }
    pub fn set_right(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        *(self.right.borrow_mut()) = v;
    }
    pub fn set_degree(&self, v: u32) {
        *(self.degree.borrow_mut()) = v;
    }
    pub fn set_mark(&self, v: bool) {
        *(self.mark.borrow_mut()) = v;
    }

    pub fn degree_inc(&self) {
        *(self.degree.borrow_mut()) = self.get_degree() + 1;
    }
    pub fn degree_dec(&self) {
        *(self.degree.borrow_mut()) = self.get_degree() - 1;
    }

    pub fn insert_child(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        if let Some(v) = v.as_ref() {
            let v_rc = Rc::clone(v);
            if let Some(child) = self.get_child().as_ref() {
                let child_rc = Rc::clone(child);
                if let Some(left_child) = child_rc.get_left().as_ref() {
                    left_child.set_right(Some(Rc::clone(v)));
                    v_rc.set_left(Some(Rc::clone(left_child)));
                } else {
                    v_rc.set_left(Some(Rc::clone(child)));
                    child_rc.set_right(Some(Rc::clone(v)));
                }
                v_rc.set_right(Some(Rc::clone(child)));
                child_rc.set_left(Some(Rc::clone(v)));
            } else {
                self.set_child(Some(Rc::clone(v)));
            }
            self.degree_inc();
        }
    }

    pub fn revome(&self) {
        if !self.is_alone() {
            let self_left = Rc::clone(self.get_left().as_ref().unwrap());
            let self_right = Rc::clone(self.get_right().as_ref().unwrap());
            self_left.set_right(Some(Rc::clone(&self_right)));
            self_right.set_left(Some(Rc::clone(&self_left)));
        }
    }
    pub fn is_root(&self) -> bool {
        self.get_p().is_none()
    }
    pub fn is_leaf(&self) -> bool {
        self.get_child().is_none()
    }
}

impl<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> fmt::Display
    for MergeableHeapNode<T>
{
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.get_key())
    }
}

pub struct MergeableHeap<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> {
    min: RefCell<Option<Rc<MergeableHeapNode<T>>>>,
    n: RefCell<u32>,
    degree: RefCell<u32>,
}

impl<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> fmt::Display for MergeableHeap<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut row = 1;
        if !(self.is_empty()) {
            let mut node_list = Vec::new();
            let mut node_list_temp = Vec::new();
            let mut node_next;
            if let Some(min_node) = self.get_min() {
                if min_node.is_alone() {
                    print!("{} -- ", min_node.get_key());
                } else {
                    node_next = Rc::clone(&min_node);
                    println!("self degree: {}", self.get_degree());
                    for _ in 0..self.get_degree() {
                        print!("{} -- ", node_next.get_key());
                        node_list.push(Rc::clone(&node_next));
                        if node_next.get_right().is_some() {
                            node_next = node_next.get_right().unwrap();
                        }
                    }
                }
            }
            println!("|  {}\n", row);
            row += 1;
            while !node_list.is_empty() {
                node_list_temp.clear();
                for node in node_list.iter() {
                    if let Some(node_child) = node.get_child() {
                        if node_child.is_alone() {
                            print!("{} --", node_child.get_key());
                            node_list_temp.push(Rc::clone(&node_child));
                        } else {
                            node_next = Rc::clone(&node_child);
                            for _ in 0..node.get_degree() {
                                print!("{} --", node_child.get_key());
                                node_list_temp.push(Rc::clone(&node_next));
                                node_next = Rc::clone(node_next.get_right().as_ref().unwrap());
                            }
                        }
                    } else {
                        print!(" Nil -- ");
                    }
                    print!("|")
                }
                println!("  {}\n", row);
                row += 1;
                node_list = node_list_temp.clone();
            }
            write!(f, "")
        } else {
            write!(f, "Empty!")
        }
    }
}

impl<T: Clone + PartialOrd + PartialEq + fmt::Display + Default> MergeableHeap<T> {
    pub fn build() -> Self {
        MergeableHeap {
            min: RefCell::new(None),
            n: RefCell::new(0),
            degree: RefCell::new(0),
        }
    }
    pub fn is_empty(&self) -> bool {
        self.get_min().is_none() || self.get_n() == 0 || self.get_degree() == 0
    }
    pub fn get_min(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        unsafe {
            if let Some(v) = &*(self.min.as_ptr()) {
                Some(Rc::clone(v))
            } else {
                None
            }
        }
    }
    pub fn get_n(&self) -> u32 {
        unsafe { *(self.n.as_ptr()) }
    }
    pub fn get_degree(&self) -> u32 {
        unsafe { *(self.degree.as_ptr()) }
    }

    pub fn set_min(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        *(self.min.borrow_mut()) = v;
    }
    pub fn set_n(&self, v: u32) {
        *(self.n.borrow_mut()) = v;
    }
    pub fn set_degree(&self, v: u32) {
        *(self.degree.borrow_mut()) = v;
    }
    pub fn n_inc(&self) {
        *(self.n.borrow_mut()) = self.get_n() + 1;
    }
    pub fn n_dec(&self) {
        *(self.n.borrow_mut()) = self.get_n() - 1;
    }
    pub fn degree_inc(&self) {
        *(self.degree.borrow_mut()) = self.get_degree() + 1;
    }
    pub fn degree_dec(&self) {
        *(self.degree.borrow_mut()) = self.get_degree() - 1;
    }
    pub fn root_insert_child(&self, v: Option<Rc<MergeableHeapNode<T>>>) {
        if let Some(v) = v.as_ref() {
            let v_rc = Rc::clone(v);
            v_rc.set_p(None);
            if self.is_empty() {
                self.set_min(Some(Rc::clone(v)));
                v.set_left(None);
                v.set_right(None);
            } else {
                let root = Rc::clone(self.get_min().as_ref().unwrap());
                if let Some(root_left) = root.get_left().as_ref() {
                    root_left.set_right(Some(Rc::clone(&v)));
                    v.set_left(Some(Rc::clone(root_left)));
                } else {
                    v.set_left(Some(Rc::clone(&root)));
                    root.set_right(Some(Rc::clone(v)));
                }
                v.set_right(Some(Rc::clone(&root)));
                root.set_left(Some(Rc::clone(v)));
                if v.get_key() < root.get_key() {
                    self.set_min(Some(Rc::clone(v)));
                }
            }
            self.degree_inc();
        }
    }

    pub fn fib_heap_insert(&self, x: Option<Rc<MergeableHeapNode<T>>>) {
        self.root_insert_child(x);
        self.n_inc();
    }
    pub fn fib_heap_min(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        if let Some(min) = self.get_min().as_ref() {
            Some(Rc::clone(min))
        } else {
            None
        }
    }
    pub fn fib_heap_union(h1: MergeableHeap<T>, h2: MergeableHeap<T>) -> MergeableHeap<T> {
        let h = MergeableHeap::build();
        if h1.is_empty() {
            h.set_min(h2.get_min());
        } else if h2.is_empty() {
            h.set_min(h1.get_min());
        } else {
            h.set_min(h1.get_min());
            let h_min = Rc::clone(h.get_min().as_ref().unwrap());
            let h2_min = Rc::clone(h2.get_min().as_ref().unwrap());
            if let Some(h_min_left_ref) = h_min.get_left().as_ref() {
                let h_min_left = Rc::clone(h_min_left_ref);
                if let Some(h2_min_left_ref) = h2_min.get_left().as_ref() {
                    let h2_min_left = Rc::clone(h2_min_left_ref);
                    h_min_left.set_right(Some(Rc::clone(&h2_min_left)));
                    h2_min_left.set_right(Some(Rc::clone(&h_min_left)));
                    h_min.set_left(Some(Rc::clone(&h2_min)));
                    h2_min.set_left(Some(Rc::clone(&h_min)));
                } else {
                    h_min_left.set_right(Some(Rc::clone(&h2_min)));
                    h_min.set_left(Some(Rc::clone(&h2_min)));
                    h2_min.set_left(Some(Rc::clone(&h_min_left)));
                    h2_min.set_right(Some(Rc::clone(&h_min)));
                }
            } else {
                if let Some(h2_min_left_ref) = h2_min.get_left().as_ref() {
                    let h2_min_left = Rc::clone(h2_min_left_ref);
                    h_min.set_left(Some(Rc::clone(&h2_min_left)));
                    h_min.set_right(Some(Rc::clone(&h2_min)));
                    h2_min_left.set_right(Some(Rc::clone(&h_min)));
                    h2_min.set_left(Some(Rc::clone(&h_min)));
                } else {
                    h_min.set_left(Some(Rc::clone(&h2_min)));
                    h_min.set_right(Some(Rc::clone(&h2_min)));
                    h2_min.set_right(Some(Rc::clone(&h_min)));
                    h2_min.set_left(Some(Rc::clone(&h_min)));
                }
            }
        }
        h.set_n(h1.get_n() + h2.get_n());
        h.set_degree(h1.get_degree() + h2.get_degree());
        h
    }
    pub fn fib_heap_link(
        &self,
        y: Option<Rc<MergeableHeapNode<T>>>,
        x: Option<Rc<MergeableHeapNode<T>>>,
    ) {
        if let Some(y_ref) = y.as_ref() {
            let y = Rc::clone(y_ref);
            if let Some(x_ref) = x.as_ref() {
                let x = Rc::clone(x_ref);
                y.revome();
                y.set_p(Some(Rc::clone(&x)));
                y.set_mark(false);
                x.insert_child(Some(Rc::clone(&y)));
            }
        }
    }
    pub fn consolidate(&self) {
        let len = (((self.get_n() as f32).log((1.0 + 5.0_f32.sqrt()) / 2.0) as u32) + 1) as usize;
        let mut a: Vec<Option<Rc<MergeableHeapNode<T>>>> = vec![None; len];
        let mut x = self.get_min();
        let self_degree = self.get_degree() as usize;
        let mut w_list = vec![None; self_degree];
        let mut x_rc;
        for i in 0..self_degree {
            x_rc = Rc::clone(x.as_ref().unwrap());
            w_list[i] = Some(Rc::clone(&x_rc));
            x = x_rc.get_right();
        }
        let mut temp;
        let mut x_rc;
        for i in 0..self_degree {
            temp = Rc::clone(w_list[i].as_ref().unwrap());
            x_rc = Rc::clone(&temp);
            let mut d = temp.get_degree() as usize;
            while !a[d].is_none() {
                let mut y = Rc::clone(a[d].as_ref().unwrap());
                if x_rc.get_key() > y.get_key() {
                    temp = Rc::clone(&x_rc);
                    x_rc = Rc::clone(&y);
                    y = temp;
                }
                self.fib_heap_link(Some(Rc::clone(&y)), Some(Rc::clone(&x_rc)));
                self.degree_dec();
                a[d] = None;
                d += 1;
            }
            println!("{}", self);
            a[d] = Some(Rc::clone(&x_rc));
        }
        self.set_degree(0);
        self.set_min(None);
        for i in 0..len {
            if !a[i].is_none() {
                self.root_insert_child(Some(Rc::clone(a[i].as_ref().unwrap())));
            }
        }
    }
    pub fn fib_remin(&self) {
        println!("ReMin");
        if let Some(z_rc) = self.get_min().as_ref() {
            let mut min = Rc::clone(z_rc);
            if !min.is_alone() {
                if min.get_right().is_some() {
                    let mut node_next = min.get_right().unwrap();
                    for _ in 0..self.get_degree() {
                        println!("{}", node_next);
                        if node_next.get_key() < min.get_key() {
                            min = Rc::clone(&node_next);
                        }
                        if node_next.get_right().is_some() {
                            node_next = Rc::clone(&node_next.get_right().unwrap())
                        }
                    }
                }
            }
            self.set_min(Some(Rc::clone(&min)));
        }
        println!("ReMin Over");
    }
    pub fn fib_heap_extract_min(&self) -> Option<Rc<MergeableHeapNode<T>>> {
        let z = self.get_min();
        if self.get_n() == 1 || self.get_degree() == 1 {
            self.set_min(None);
            self.set_n(0);
            self.set_degree(0);
        } else {
            if let Some(z_ref) = self.get_min().as_ref() {
                let z = Rc::clone(z_ref);
                if let Some(z_child_ref) = z.get_child().as_ref() {
                    let z_child = Rc::clone(z_child_ref);
                    if z_child.is_alone() {
                        self.root_insert_child(Some(Rc::clone(&z_child)));
                    } else {
                        let mut z_child_next = Rc::clone(z_child_ref);
                        let mut temp;
                        for _ in 0..self.get_degree() {
                            temp = Rc::clone(z_child_next.get_right().as_ref().unwrap());
                            self.root_insert_child(Some(Rc::clone(&z_child_next)));
                            z_child_next = Rc::clone(&temp);
                        }
                    }
                    z.revome();
                    self.consolidate();
                } else {
                    if let Some(z_right_ref) = z.get_right().as_ref() {
                        let z_right = Rc::clone(z_right_ref);
                        self.set_min(Some(Rc::clone(&z_right)));
                        z.revome();
                    } else {
                        self.set_min(None);
                    }
                }
                self.n_dec();
                self.degree_dec();
            }
        }
        z
    }
    pub fn cut(&self, x: Option<Rc<MergeableHeapNode<T>>>, y: Option<Rc<MergeableHeapNode<T>>>) {
        if let Some(x_ref) = x.as_ref() {
            let x = Rc::clone(x_ref);
            if let Some(y_ref) = y.as_ref() {
                let y = Rc::clone(y_ref);
                x.revome();
                y.degree_dec();
                if y.get_degree() == 0 {
                    y.set_child(None);
                } else {
                    y.set_child(x.get_right());
                }
                x.set_mark(false);
                self.root_insert_child(Some(Rc::clone(&x)));
                println!("{}", self);
            }
        }
    }
    pub fn cascading_cut(&self, y: Option<Rc<MergeableHeapNode<T>>>) {
        if let Some(y_ref) = y.as_ref() {
            let y = Rc::clone(y_ref);
            if let Some(z_ref) = y.get_p().as_ref() {
                let z = Rc::clone(z_ref);
                if y.get_mark() == false {
                    y.set_mark(true);
                } else {
                    self.cut(Some(Rc::clone(&y)), Some(Rc::clone(&z)));
                    self.cascading_cut(Some(Rc::clone(&z)));
                }
            }
        }
    }
    pub fn fib_heap_decrease_key(&self, x: Option<Rc<MergeableHeapNode<T>>>, k: T) {
        if let Some(x_ref) = x.as_ref() {
            let x = Rc::clone(x_ref);
            if k > x.get_key() {
                println!("new key is greater than current key!");
            }
            x.set_key(k);
            if let Some(y_ref) = x.get_p().as_ref() {
                let y = Rc::clone(y_ref);
                if x.get_key() < y.get_key() {
                    self.cut(Some(Rc::clone(&x)), Some(Rc::clone(&y)));
                    self.cascading_cut(Some(Rc::clone(&y)));
                }
            }
        }
    }
    pub fn fib_heap_delete(&self, x: Option<Rc<MergeableHeapNode<T>>>) {
        self.fib_heap_decrease_key(x, T::default());
        self.fib_heap_extract_min();
    }
}
/*
    let tree: MergeableHeap<u32> = MergeableHeap::build();
    let a = MergeableHeapNode::build(100).get_self_ptr();
    tree.fib_heap_insert(MergeableHeapNode::build(4).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(12).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(45).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(23).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(1).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(17).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(11).get_self_ptr());
    tree.fib_heap_insert(MergeableHeapNode::build(8).get_self_ptr());
    tree.fib_heap_insert(a);
    println!("{}", tree);
    tree.fib_heap_extract_min();
    println!("{}", tree);
    tree.fib_heap_extract_min();
    println!("{}", tree);
    let tree2: MergeableHeap<u32> = MergeableHeap::build();
    tree2.fib_heap_insert(MergeableHeapNode::build(67).get_self_ptr());
    println!("{}", tree2);
    let tree3 = MergeableHeap::fib_heap_union(tree, tree2);
    println!("{}", tree3);
    tree3.fib_heap_decrease_key(a, 3);
    println!("{}", tree3);
    tree3.fib_heap_delete(a);
    println!("{}", tree3);
*/
